15.3 Регуляризация в онлайн-обучении

В этом параграфе мы поговорим о регуляризации, но использовать мы её будем не для стабилизации обучения, а для того, чтобы накладывать ограничение на получаемое нами решение. Чтобы отличать их от стабилизирующих слагаемых, для таких регуляризаторов будем использовать обозначение ψt(w)\psi_t(w)

В теории от регуляризатора требуется только выпуклость, но на практике широко используются лишь три вида:

  • L1=w1L_1 = \vert\vert w\vert\vert_1 и его собрат L1/2L_{1/2};
  • L2=w22L_2 = \vert\vert w\vert\vert_2^2;
  • Проекция на выпуклое множество χ\chi:

ψ(w)=Iχ(w)={w∉χ0wχ\psi(w) = I_{\chi}(w) = \begin{cases} \infty & w \not\in \chi \\ 0 & w \in \chi \end{cases}

Классическим способом введения регуляризации является прибавление к оптимизируемому функционалу:

f^t(w)=ft(w)+ψt(w)\hat{f}_t(w) = f_t(w) + \psi_t(w)

с последующим применением любых методов оптимизации «из коробки». Яркий пример — L2L_2 регуляризация:

f^t(w)=ft(w)+12λ2w22,\hat{f}_t(w) = f_t(w) + \frac{1}{2\lambda_2}\vert\vert w\vert\vert_2^2,

которая не портит гладкости функционала.

Идея неразложения регуляризаторов в субградиентную оценку

Вспомним вывод linearized FTRL. В ходе линеаризации мы заменяли все функции f^t(w)\hat{f}_t(w) на их субградиентную оценку в точке wtw_t. Для регуляризованного функционала f^t(w)=ft(w)+ψt(w)\hat{f}_t(w) = f_t(w) + \psi_t(w) получалась бы такая оценка:

f^t(w)f^t(wt)+(gt+ψt)T(wwt),\hat{f}_t(w) \geq \hat{f}_t(w_t) + (g_t + \partial\psi_t)^T (w - w_t),

где через ψt\partial\psi_t мы обозначили для краткости субградиент ψt\psi_t в точке wtw_t. Теперь субградиентную оценку можно подставить в метод FTRL:

wt+1=argminw[(g1:t+ψ1:t)Tw+s=1twwsσs2]w_{t+1} = arg\min\limits_w \Big[(g_{1:t} + \partial\psi_{1:t})^Tw + \sum\limits_{s=1}^t\vert\vert w - w_s\vert\vert_{\sigma_s}^2\Big]

Идея неразложения состоит в следующем: заменим на субградиентную оценку только ft(w)f_t(w), а регуляризатор будем подбирать так, чтобы задача FTRL решалась аналитически. Интуитивно, оценка

f^t(w)=ft(w)+ψt(w)ft(wt)+gtT(wwt)+ψt(w)\hat{f}_t(w) = f_t(w) + \psi_t(w) \geq f_t(w_t) + g_t^T(w - w_t) + \psi_t(w)

должна быть точнее оценки

f^t(w)=ft(w)+ψt(w)ft(wt)+ψt(wt)+(gt+ψt)T(wwt)\hat{f}_t(w) = f_t(w) + \psi_t(w) \geq f_t(w_t) + \psi_t(w_t) + (g_t + \partial\psi_t)^T (w - w_t)

а значит, и метод оптимизации будет точнее и эффективнее.

Эта идея очень важна для построения регуляризованных алгоритмов онлайн-обучения.

Давайте выпишем, как будут выглядеть с учётом этой идеи регуляризованные алгоритмы.

Composite Objective FTRL

wt+1=argminw[g1:tTw+ψ1:t(w)+s=1twwsσs2]w_{t+1} = arg\min\limits_w \Big[g_{1:t}^Tw + \psi_{1:t}(w) + \sum\limits_{s=1}^t\vert\vert w - w_s\vert\vert_{\sigma_s}^2\Big]

Online Mirror Descent, Proximal Gradient Descent, (F)ISTA

wt+1=argminw[gtTw+ψt(w)+wwtσt2]w_{t+1} = arg\min\limits_w \Big[g_t^Tw + \psi_t(w) + \vert\vert w - w_t\vert\vert_{\sigma_t}^2 \Big]

Напомним, что три названия в заголовке соответствуют трём способам восприятия этой формулы:

  • Online Mirror Descent — метод онлайн-обучения;
  • Proximal Gradient Descent — метод (стохастической) батч-оптимизации. В стохастическом случае он неотличим от Mirror Descent;
  • (F)ISTA — по сути, это название аналитического решения указанного уравнения для L1L_1-регуляризации.

Связь между Composite-Objective FTRL и Proximal Gradient Descent. Lazy vs Greedy представления

В этом подразделе мы будем проводить рассуждения на примере L1L_1-регуляритора. для других регуляризаторов выкладки будут аналогичными.

Выпишем Proximal (он же Mirror) Gradient Descent с L1L_1-регуляризацией:

wt+1=argminwgtTw+λ1w1+12ηtwwt22w_{t+1} = arg\min\limits_w g_t^Tw + \lambda_1\vert\vert w\vert\vert_1 + \frac{1}{2\eta_t}\vert\vert w - w_t\vert\vert_2^2

Необходимым условием минимума явняется равенство нулю градиента (а в данном случае субградиента) всего выражения:

0=gt+g^t+1ηt(wt+1wt)0 = g_t + \hat{g}_t + \frac{1}{\eta_t}(w_{t+1} - w_t)

где g^t\hat{g}_t - субградиент регуляризатора λ1w1\lambda_1\vert\vert w\vert\vert_1 в точке wtw_{t}. Отсюда получаем

wt+1=wtηt(gt+g^T)w_{t+1} = w_{t} - \eta_t (g_t + \hat{g}^T)

Если же переписать формулы в духе FTRL, мы получим

wt+1=argminwg1:tTw+g^1:t1Tw+λw1+12s=0twwsσs2w_{t+1} = arg\min\limits_{w} g_{1:t}^Tw + \hat{g}_{1:{t-1}}^Tw + \lambda \vert\vert w\vert\vert_1 + \frac{1}{2}\sum\limits_{s=0}^t\vert\vert w-w_s\vert\vert_{\sigma_s}^2

Получился метод, который оптимизирует L1L_1-регуляризатор в явном виде только на текущей итерации tt, а для остальных использует субоптимальные субградиентные оценки. Заметим, что тем же выражением можно ограничить сверху и функционал:

wt+1=argminwg1:tTw+tλw1+12s=0twwsσs2w_{t+1} = arg\min\limits_{w} g_{1:t}^Tw + t\lambda \vert\vert w\vert\vert_1 + \frac{1}{2}\sum\limits_{s=0}^t\vert\vert w-w_s\vert\vert_{\sigma_s}^2

Мы получили метод FTRL с incremental L1L_1 — более сильным и стабильным вариантом регуляризации, чем Mirror Descent. Подробнее его анализом мы займемся в параграфе про продвинутую L1L_1-регуляризацию.

L1L_1-регуляризация

Отбор параметров разреженных моделей

Предположим, что мы хотим обучить модель минимального размера и при этом как можно лучшего качества. В этом нам поможет отбор параметров. А именно, давайте постараемся оставить только те из них, которые оказывают наиболее влияние на лосс f1:T(w)f_{1:T}(w).

Определение. Будем называть параметр wiw_i разреженным, если он не используется (пропускается) при предсказании некоторых ft(w)f_t(w). «Некоторых» может означать как десятую часть, так и 0.999990.99999 прогнозов ft(w)f_t(w), главное — что такие объекты просто есть. Частым мы будем называть параметр, у которого частота пропусков низкая (например, 10%10\% пропусков), а редким — тот, у которого она высокая (второй случай).

Пример. Рассмотрим модель разреженной линейной регрессии ft(w)=(wTxtyt)2f_t(w) = (w^Tx_t - y_t)^2. Обычно она применяется в ситуациях, когда элементы вектора признаков xt,ix_{t,i} — это 00 или 11 (например, «встретилось ли ii-е слово в tt-м документе»), причем на практике доля единиц обычно бывает очень маленькой. Поэтому существенная часть параметров wiw_i при прогнозе на шаге tt будет умножаться на нули и, таким образом, не будет использоваться.

Обратите внимание: как правило, в литературе по онлайн-обучению говорят о разреженных параметрах, а не признаках. Впрочем, подавляющее большинство моделей на разреженных признаках устроены так, что каждому такому признаку сопоставляется некий набор параметров, поэтому определения «разреженный признак» и «разреженные параметры» взаимозаменяемы. В линейной модели, как в примере выше, каждому признаку xix_i сопоставляется параметр wiw_i. В более сложных моделях признаку xix_i может сопоставляться вектор параметров wiw_i — эмбеддинг этого признака.

Давайте теперь поймём, что означает фраза «признак влияет на лосс f1:T(w)f_{1:T}(w)». Оказывать влияние можно двумя способами:

  1. Качеством. Если параметр wiw_i редкий, но очень хорошо прогнозирует свой небольшой набор объектов, его стоит оставить. За счет того, что мы оставим достаточное количество таких параметров, мы можем покрыть большое число объектов. Такие параметры называются memorization parameters (они как будто запоминают «свои» объекты).
  2. Количеством. Если параметр wiw_i часто встречается, то он в любом случае должен остаться в модели и помогать с суммарным качеством прогноза.

Убирать мы хотим только слабые и редкие параметры. Таких, как правило, больше 99%99\%.

Обратите внимание: мы не хотим убирать слабые, но часто встречающиеся параметры. Тому есть две причины:

  1. Места они много не занимают, а количества данных в large scale задачах достаточно, чтобы правильно выучить эти параметры. Они будут вносить свой, пусть и небольшой, вклад в общее качество;
  2. Частые параметры хорошо запоминают среднее поведение на всех данных, а разреженные — поведение на конкретных объектах. Если наша цель — оставить как можно меньше параметров, то выгоднее хорошо выучить среднее поведение на всех данных, а отклонения от среднего запомнить с помощью memorization parameters. Если в модели есть только супер-разреженные параметры, то из-за огромной вариативности в их возможных комбинациях в данных каждому параметру придется доучивать среднее поведение. Подробнее на этой проблеме мы остановимся в конце параграфа.

Инициализация разреженных параметров

В обучении разреженных моделей все параметры, на которые накладывается L1L_1-регуляризация, инициализируются нулями. С точки зрения здравого смысла такая инициализация довольно естественна, однако есть и более формальное обоснование;

  1. Если параметры инициализируются нулями, то мы по мере обучения смотрим на градиенты этих параметров и в зависимости от градиентов принимаем решение, нужен нам параметр для прогноза или не нужен. Все параметры стартуют в равных условиях, и модель понемногу выходит из состояния «абсолютная разреженность», выучивая что-то содержательное.
  2. Если же параметры инициализируются случайно, то нам надо сначала доучить все параметры до какого-то более или менее разумного значения, а потом уже пытаться понять, нужен ли он нам. Момент, когда модель начинает эффективно разреживаться, тем самым очень сильно отдалается.

Composite-objective FTRL с L1L_1-регуляризацией

Напомним формулировку задачи:

wt+1=argminwg1:tTw+λ1,tw1+12s=1Twwsσs2w_{t+1} = arg\min\limits_w g_{1:t}^Tw + \lambda_{1,t}\vert\vert w\vert\vert_1 + \frac{1}{2}\sum\limits_{s=1}^T\vert\vert w - w_s\vert\vert_{\sigma_s}^2

Решение можно выписать в явном виде. Для этого введём следующие обозначения:

  • ztz_t будет аккумулировать сумму градиентов, z0=0z_0 = 0,
  • ntn_t будет аккумулировать сумму поэлементных квадратов градиентов, n0=0n_0 = 0,
  • α\alpha — это learning rate.

Следующие формулы выписаны отдельно для каждой координаты. В них ii — индекс параметра модели, tt — номер итерации.

σt,i=1ηt,i1ηt1,i=1α(nt,i+gt,i2nt,i)\sigma_{t,i} = \frac{1}{\eta_{t,i}} - \frac{1}{\eta_{t-1,i}} = \frac{1}{\alpha}\Big(\sqrt{n_{t,i} + g_{t,i}^2} - \sqrt{n_{t,i}}\Big)

zt+1,i=zt,i+gt,iσt,iwt,iz_{t+1,i} = z_{t,i} + g_{t,i} - \sigma_{t,i}w_{t,i}

nt+1,i=nt,i+gt,i2n_{t+1,i} = n_{t,i} + g_{t,i}^2

wt+1,i={0zt+1,iλ1,tαnt+1,i+αλ2,t(zt+1,isgn(zt+1,i)λ1,t)zt+1,i>λ1,t()w_{t+1,i} = \begin{cases} 0 & \vert z_{t+1,i}\vert \leq \lambda_{1,t}\\ -\frac{\alpha}{\sqrt{n_{t+1,i}} + \alpha\lambda_{2,t}} \Big(z_{t+1,i} - sgn(z_{t+1,i})\lambda_{1,t} \Big) & \vert z_{t+1,i}\vert > \lambda_{1,t} \end{cases}\qquad(\ast)

Вывод этих формул хорошо расписан в конспекте курса Д. А. Кропотова.

Анализ аналитического решения

При регуляризаторе w1\vert\vert w\vert\vert_1 в оптимизируемом функционале стоят коэффициенты λ1,t\lambda_{1,t}, которые могут как-то зависеть от tt. Обычно рассматривают три вида зависимости:

  1. Fixed: λ1,t=λ\lambda_{1,t} = \lambda.
  2. Squared incremental: λ1,t=tλ\lambda_{1,t} = \sqrt{t}\lambda
  3. Linear incremental: λ1,t=tλ\lambda_{1,t} = t\lambda

Их также можно комбинировать, получая коэффициенты регуляризации

λ1,t=λ1,global+tλ1,sqrt+tλ1,incremental\lambda_{1,t} = \lambda_{1,global} + \sqrt{t}\lambda_{1,sqrt} + t\lambda_{1,incremental}

Напомним, что все веса wiw_{i} мы инициализируем нулями. По формулам ()(\ast) из нуля на шаге tt выводятся веса wiw_i, для которых

g1:t,iσsws,i>λ1,t.\vert g_{1:t,i} - \sum\limits\sigma_sw_{s,i}\vert > \lambda_{1,t}.

Таким образом, начальное условие выхода параметров из нуля имеет вид

g1:t,i>λ1,t.\vert g_{1:t,i}\vert > \lambda_{1,t}.

Попробуем понять физический смысл этого неравенства.

Напоминание. Говорят, что функция f(w)f(w) имеет липшиц-непрерывный градиент с константой LL, если

f(x)f(y)22L2xy22\vert\vert \nabla f(x) - \nabla f(y)\vert\vert_2^2 \leq \frac{L}{2} \vert\vert x - y\vert\vert_2^2

Предположим, что это выполняется (ниже мы покажем, что это не слишком обременительное ограничение). Тогда, подставив в качестве yy точку оптимума функции ft(w)f_t(w) (не путайте с глобальным wTw_T^* из regret!), мы получим

f(x)22L2xx22\vert\vert \nabla f(x)\vert\vert_2^2 \leq \frac{L}{2}\vert\vert x - x_*\vert\vert_2^2

Это означает, что для достаточно хорошей функции норма градиента является оценкой снизу на расстояние до точки оптимума в пространстве параметров. Чем больше норма градиента, тем дальше мы от оптимальных параметров ww.

Вернемся к выражению g1:t,i>λ1,t\vert g_{1:t,i}\vert > \lambda_{1,t}. Здесь мы имеем дело (а) отдельно с каждой из координат и (б) с нормой суммы градиентов (а не с суммой норм). Хорошая новость: утверждение выше верно и для функций одной переменной, то есть gs,i\vert g_{s,i}\vert, грубо говоря, показывает, насколько мы далеки от оптимума по ii-й координате. Знак gs,ig_{s,i} говорит о том, в какую сторону мы будем сдвигаться по ii-й координате ww на ss-м шаге. Если сдвиги были в основном в одну сторону, то g1:t,ig_{1:t,i} будет больше, а если они всё время в разную сторону, то отдельные слагаемые могут скомпенсировать друг друга, и g1:t,ig_{1:t,i} может быть малым.

Отметим ещё, что абсолютная величина компоненты g1:t,ig_{1:t,i} на первых итерациях может отражать прогнозирующую силу параметра wiw_i: в самом деле, неверное значение важного для предсказания параметра может вести к большим ошибкам, что будет давать большие градиенты.

Посмотрим теперь, как будет вести себя разреженная модель в зависимости от вида λ1,t\lambda_{1,t}.

Linear incremental (λ1,t=tλ1\lambda_{1,t} = t\lambda_1)

Условие выхода wiw_i из нуля принимает вид

g1:t,i>tλ1,\vert g_{1:t,i}\vert > t\lambda_1,

что равносильно

1tg1:t,i>λ1\left| \frac{1}{t}g_{1:t,i}\right| > \lambda_1

Ограничение на среднее значение компоненты градиента означает, что для выхода из нуля параметр wiw_i должен иметь определённую прогнозирующую силу. Это противоречит нашему требованию о том, чтобы частые маломощные параметры все равно присутствовали в модели и выучивали среднее поведение.

Обратите внимание. Выше мы показали, что проксимальный градиентный спуск с обычным L1L_1

wt+1=argminwgtTw+λ1w1+1ηtwwt22w_{t+1} = arg\min\limits_w g_t^Tw + \lambda_1 \vert\vert w\vert\vert_1 + \frac{1}{\eta_t}\vert\vert w - w_t\vert\vert_2^2

в некотором смысле эквивалентен Composite-Objective FTRL с инкрементальным L1L_1. Таким образом, обычная L1L_1-регуляризация в классическом градиентном спуске эквивалентна именно инкрементальному L1L_1, который, как мы выяснили, субоптимален. Ниже мы рассмотрим специфический для FTRL вариант L1L_1-регуляризации, который лишен этих недостатков.

Фиксированный (λ1,t=tλ1\lambda_{1,t} = t\lambda_1)

Это самый мощный и полезный на практике режим.

Здесь мы не нормируем на 1t\frac{1}{t} (то есть не берём среднее), и это означает, что выйти из нуля может и слабый, но частый параметр, который за много итераций накопит достаточно большую сумму частных производных.

Свойства фильтрации с фиксированным регуляризатором в точности совпадают с продуктовыми требованиями:

  1. Редкий параметр с мощной прогнозирующей силой на старте будет иметь большие по модулю градиенты одного знака, и он выйдет из нуля;
  2. Редкий параметр с малой прогнозной силой не выйдет из нуля;
  3. Частые параметры в любом случае выйдут из нуля.

Squared incremental: (λ1,t=tλ\lambda_{1,t} = \sqrt{t}\lambda)

В этой статье было теоретически обосновано, что если параметр частый, но нерелевантный и абсолютно шумный, то дисперсия g1:t\vert g_{1:t}\vert будет иметь асимптотику O(t)O(\sqrt{t}). Из этого следует, что, если сделать регуляризацию порядка t\sqrt{t}, мы лишим такой случайный шум почти любых шансов выйти из нуля.

К сожалению, ни в игрушечных примерах вроде Avazu, ни в продакшен задачах улучшений качества прогноза или степени разреживания модели без потери качества достичь не удалось. Возможно, вам повезет больше.

Полезность частых параметров для разреживания модели

Рассмотрим две линейных модели

ft(w)=wTxt+b,gt(w)=wTxt,f_t(w) = w^Tx_t + b,\quad g_t(w) = w^Tx_t,

в которых все параметры wiw_i разреженные. Давайте считать, что в первой модели есть константный (и совсем даже не разреженный) признак xb=1x_b = 1, которому и соответствует параметр bb.

Теперь в каждой из моделей наложим на ww регуляризацию L1L_1 и сравним, что получится:

  1. В модели ftf_t параметрам wiw_i нужно запомнить «отклонение» от среднего bb;
  2. В модели gtg_t параметрам wiw_i нужно запомнить абсолютное значение предсказания.

Нетрудно понятно, что при наличии bias нормы градиентов в первой модели в среднем будут намного меньше, потому что мы на каждом шаге оптимизации будем стартовать с точки, которая в среднем ближе к точке оптимума (bias и есть наше среднее). Поэтому меньше весов смогут преодолеть порог по модулю суммы градиентов и выйти из нуля. Таким образом, несмотря на одинаковый оптимум без регуляризации, при введении L1L_1-регуляризации модель с bias будет обладать более хорошим соотношением разреженность/качество прогноза.

Эта логика легко обобщается на более сложные случаи, когда вместо bias у нас есть неразреженные контентные признаки. Вывод такой: модели, в которых есть только очень разреженные параметры, обладают гораздо худшим соотношением разреженность/качество, чем модели, в которых есть и контентные, и разреженные параметры.

Убедиться в этих эффектах мы сможем в разделе с практикой на линейных моделях.

L2L_2 регуляризация

Weight decay

Рассмотрим обыкновенный SGD.

wt+1=wtαgtw_{t+1} = w_t - \alpha g_t

Weight decay состоит во введение штрафа на размер текущих весов:

wt+1=(1λ)wtαgt,0λ<1w_{t+1} = (1 - \lambda)w_t - \alpha g_t,\quad 0 \leq \lambda < 1

Внимательные читатели уже заметили, что в случае с SGD это эквивалентно введению L2L_2-регуляризации. Давайте разберёмся, как это сделать правильно.

Decoupled weight decay

Попробуем заменить ft(w)f_t(w) на

f^t(w)=ft(w)+λ2w22\hat{f}_t(w) = f_t(w) + \lambda_2 \vert\vert w\vert\vert_2^2

и запустить любой адаптивный метод, например, AdaGrad. Если мы беспечно заменим на градиентную оценку всю функцию f^t(w)\hat{f}_t(w) (забыв, что с регуляризатором этого делать не стоит), то алгоритм примет вид

wt+1=wtη^tgt,w_{t+1} = w_t - \hat{\eta}_tg_t,

где

η^t=αs=1t(gs+λ2ws)2\hat{\eta}_t = \frac{\alpha}{\sqrt{\sum\limits_{s=1}^t (g_s + \lambda_2 w_s)^2 }}

В этих формулах нехороши две вещи:

  1. Коэффициенты α\alpha и λ2\lambda_2 нетривиальным образом взаимодействуют. Это крайне неудобно при переборе гиперпараметров: изменение learning rate α\alpha должно влечь за собой переподбор коэффициента регуляризации λ2\lambda_2 по полной сетке;
  2. В квадратах градиентов мы хотим видеть только адаптивность к кривизне самой функции ftf_t, но теперь там ещё добавка λ2ws\lambda_2w_s.

Эта проблема была впервые замечена в Decoupled weight decay regularization. Авторы также рассматривали влияние на momentum, к этому мы вернёмся в параграфе про AdamW.

Авторы статьи предлагают модифицировать метод AdaGrad следующим образом:

wt+1=wtαs=1tgs2gtλ2wtw_{t+1} = w_t - \frac{\alpha}{\sqrt{\sum\limits_{s=1}^t g_s^2}} g_t - \lambda_2 w_t

Сразу отметим сходство с исходными формулами weight decay — его и добивались авторы.

Decoupled weight decay — это адаптивный L2L_2

Легко видеть, что формула

wt+1=wtαs=1tgs2gtλ2wtw_{t+1} = w_t - \frac{\alpha}{\sqrt{\sum\limits_{s=1}^t g_s^2}} g_t - \lambda_2 w_t

описывает обыкновенный покоординатный градиентный спуск с некоторым линеаризованным L2L_2-регуляризатором. Давайте «проинтегрируем» это выражение обратно до аргминимума, из которого бы получились такие формулы обновления весов:

wt+1=argminw[gtTw+λ2ηtwtTw+12ηtwwt22]w_{t+1} = arg\min\limits_w \Big[ g_t^Tw + \frac{\lambda_2}{\eta_t}\color{#E06A27}{w_t^T}w + \frac{1}{2\eta_t}\vert\vert w - w_t\vert\vert_2^2 \Big]

Получается, что decoupled weight decay — это адаптивный L2L_2-centered регуляризатор. Его можно усовершенствовать, вспомним наше важное правило не заменять регуляризатор на субградиентную оценку. Перейдём к задаче

wt+1=argminw[gtTw+λ22ηtw22+12ηtwwt22]w_{t+1} = arg\min\limits_w \Big[ g_t^Tw + \frac{\lambda_2}{2\eta_t}\vert\vert w\vert\vert_2^2 + \frac{1}{2\eta_t}\vert\vert w - w_t\vert\vert_2^2 \Big]

Она отличается от предыдущей заменой wtTw\color{#E06A27}{w_t^T}w на wTw=w2\color{#348FEA}{w^T}w = \vert\vert w\vert\vert^2. Её решение имеет вид

wt+1=11+λ2(wtηtgt)w_{t+1} = \color{#C81D6B}{\frac{1}{1 + \lambda_2}}\Big(w_t - \eta_t g_t \Big)

Поскольку мы меньше огрубляем оптимизируемый функционал, обучение может стать немного стабильнее.

Обратите внимание, что в оптимизационной задаче у нас теперь стоит не просто λ2\lambda_2, а λ22ηt\frac{\lambda_2}{2\eta_t}.

Decoupled L2L_2-регуляризация в Composite-Objective FTRL

Теперь посмотрим, как decoupled weight decay будте работать с Composite-Objective FTRL. Линеаризованная задача имеет вид:

wt+1=argminw[g1:tTw+λ22wσ1:s2+12s=1twwsσs2]w_{t+1} = arg\min\limits_w \left[g_{1:t}^Tw + \frac{\lambda_2}{2}\vert\vert w\vert\vert_{\sigma_{1:s}}^2 + \frac{1}{2}\sum\limits_{s=1}^t\vert\vert w - w_s\vert\vert_{\sigma_s}^2\right]

Перепишем её:

wt+1=argminw[g1:tTw+12s=1t(wwsσs2+λ2wσs2)]w_{t+1} = arg\min\limits_w \left[g_{1:t}^Tw + \frac{1}{2}\sum\limits_{s=1}^t\Big(\vert\vert w - w_s\vert\vert_{\sigma_s}^2 + \lambda_2\vert\vert w\vert\vert_{\sigma_s}^2 \Big)\right]

Нетрудно показать, что решение имеет вид

zt+1=zt+gtσtwt,z_{t+1} = z_t + g_t - \sigma_t\odot w_t,

wt+1=11+λ21ηtzt.w_{t+1} = -\color{#C81D6B}{\frac{1}{1 + \lambda_2}} \frac{1}{\eta_t}z_t.

Для ztz_t можно написать и явную формулу: zt=g1:ts=1tσswsz_{t} = g_{1:t} - \sum_{s=1}^t\sigma_s\odot w_s.

Замечание. Чтобы оценить Regret такого метода, мы не сможем механически воспользоваться оценкой для AdaGrad: ведь она базированась на оценке на Regret, выведенной либо для целиком Proximal, либо для целиком Centered L2L_2-регуляризаторов. Composite objective из теоремы 10 тут не годится, так как Centered регуляризатор в этом случае не поедет в оценку норм градиентов, а мы в текущем представлении рассматриваем Proximal и Centered как равноправные члены. Интуитивно, мы должны применить Lemma 7 к обоим регуляризаторам и получить точно такую же оценку с такой же двойственной нормой (напомним, что centered и proximal регуляризаторы имеют одинаковую двойственную норму). Двойственная норма такая же -> формулы оптимального метода AdaGrad будут такие же. Мы оставляем это читателям в качестве упражнения.

Iχ(w)I_{\chi}(w): проекция на выпуклое множество χ\chi

Напоминание: множество χ\chi называется выпуклым, если

x,yχ, α[0;1]:αx+(1α)yχ\forall x,y\in \chi,\ \forall\alpha \in [0; 1]: \quad \alpha x + (1-\alpha)y \in \chi

Проекцией на это множество называют функцию

Iχ(w)={w∉χ0wχI_{\chi}(w) = \begin{cases} \infty & w \not\in \chi \\ 0 & w \in \chi \end{cases}

Докажем, что Iχ(w)I_{\chi}(w) — выпуклый регуляризатор. Для этого нам нужно проверить неравенство

αI(x)+(1α)I(y)I(αx+(1α)y).\alpha I(x) + (1-\alpha)I(y) \geq I(\alpha x + (1 - \alpha) y).

Единственный шанс, когда это может быть нарушено — это I(αx+(1α)y)=I(\alpha x + (1 - \alpha) y) = \infty, I(x)=0I(x) = 0, I(y)=0I(y) = 0. Это значит, что x,yχx,y\in \chi, а αx+(1α)yχ\alpha x + (1 - \alpha) y \notin \chi, что противоречит выпуклости χ\chi.

Вернемся к формулам FTRL. Здесь ситуация сильно проще — от накидывания любых последовательностей α1:T\alpha_{1:T} на регуляризатор ничего не изменится, так что его всегда оставляют просто as is

wt+1=argminwg1:tTw+Iχ(w)+12s=1Twwsσs2w_{t+1} = arg\min\limits_w g_{1:t}^Tw + I_{\chi}(w) + \frac{1}{2}\sum\limits_{s=1}^T\vert\vert w - w_s\vert\vert_{\sigma_s}^2

Аналитические решения для каждого вида χ\chi нужно искать отдельно. Примерно все решения получаются путем выноса Iχ(w)I_{\chi}(w) из оптимизируемого функционала и превращения его в ограничение, после чего можно применить метод множителей Лагранжа.

Проекция на шар x:xc{x: \vert\vert x\vert\vert \leq c}

Решим аналитически задачу проекции на шар

{g1:tTw+12s=1Twwsσs2minw,w2c. \begin{cases} g_{1:t}^Tw + \frac{1}{2}\sum\limits_{s=1}^T\vert\vert w - w_s\vert\vert_{\sigma_s}^2\longrightarrow\min_w,\\ \vert\vert w\vert\vert_2 \leq c. \end{cases}

Функция Лагранжа будет иметь вид

L(w,λ)=g1:tTw+12s=1Twwsσs2+λ(w2c),L(w, \lambda) = g_{1:t}^Tw + \frac{1}{2}\sum\limits_{s=1}^T\vert\vert w - w_s\vert\vert_{\sigma_s}^2 + \lambda(\vert\vert w\vert\vert_2 - c),

а её градиент равен

wL(w,λ)=g1:tT+s=1T(wws)σs+λww2,\nabla_wL(w, \lambda) = g_{1:t}^T + \sum\limits_{s=1}^T(w - w_s)\odot\sigma_s + \lambda \frac{w}{\vert\vert w\vert\vert_2},

где σs\sigma_s - вектор, а \odot — поэлементное умножение векторов. Приравнивая к нулю градиент, получаем

zt+σ1:sw+λww2=0,z_t + \sigma_{1:s}\odot w + \lambda \frac{w}{\vert\vert w\vert\vert_2} = 0,

где мы, как обычно, обозначили zt=g1:ts=1tσswsz_{t} = g_{1:t} - \sum_{s=1}^t\sigma_s\odot w_s.

Проанализируем условие дополняющей нежесткости λ(wc)=0\lambda(\vert\vert w\vert\vert -c) = 0. Если λ=0\lambda = 0, то решение ww уже находится внутри шара и имеет вид

w=ztσ1:sw = \frac{-z_t}{\sigma_{1:s}}

При практической реализации мы просто сначала посчитаем это выражение и проверим, не попадаем ли мы в шар. Если попадаем — отлично, если нет — то дальше говорим, что w=c\vert\vert w\vert\vert = c и решаем продолжаем решение

zt+σ1:sw+λwс=0z_t + \sigma_{1:s}*w + \lambda \frac{w}{с} = 0

w=ztσ1:s+λcw = \frac{-z_t}{\sigma_{1:s} + \frac{\lambda}{c}}

Теперь подставим это в w=c\vert\vert w\vert\vert = c и получим

w=ztσ1:s+λc=c\vert\vert w\vert\vert = \frac{\vert\vert z_t\vert\vert }{\sigma_{1:s} + \frac{\lambda}{c}} = c

λ=ztσ1:sc\lambda = \vert\vert z_t\vert\vert - \sigma_{1:s}c

w=cztztw = c\frac{-z_t}{\vert\vert z_t\vert\vert }

Получаем, что если мы находимся внутри шара, то мы действуем согласно обыкновенному adaptive алгоритму со всеми хорошими свойствами, иначе — проекция побеждает.

Аналогично L1L_1 регуляризации, здесь тоже есть различия между lazy и greedy представлением этого регуляризатора. Однако, в классических DL задачах эти методы встречаются не слишком часто и здесь сложно привести какой-нибудь значимый успех, который мог бы улучшить качество в важной задача. Навскидку мы можем вспомнить разве что Adversatial White-Box learning, в котором можно было бы это попробовать.

Чтобы добавить в заметки выделенный текст, нажмите Command + E

Пройдите квиз по параграфу

Чтобы закрепить пройденный материал
Предыдущий параграф15.2. Адаптивный FTRL
Следующий параграф15.4. Методы оптимизации в Deep Learning

Вступайте в сообщество хендбука

Здесь можно найти единомышленников, экспертов и просто интересных собеседников. А ещё — получить помощь или поделиться знаниями.